package dynamicProgramming.knapsack;

/**
 * @author zxc
 * @date 2023/01/27 22:14
 **/

/**
 * 题目 ：排列的数目
 * 题目详述 ：
 * 给定一个由 不同正整数组成的数组 nums ，和一个目标整数 target 。
 * 请从 nums 中找出并返回总和为 target 的元素组合的个数。
 * 数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
 * 题目数据保证答案符合 32 位整数范围。
 *
 * 提示：
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 1000
 * nums 中的所有元素 互不相同
 * 1 <= target <= 1000
 *
 */
public class CombinationSum {
    /**
     * 思路 ：
     * 状态转移方程 ：
     * 假设f(i)为目标值为i的所有可能排列数;
     * （1）特殊情况 ：若是f(0)的情况（即，目标值为0的情况），即所有可能的排列数为1;
     * ===> 即，空排列的情况;
     * （2）一般情况 ：若是求取f(i)的话，则需要进行分类讨论;
     * f(i) = add[f(i - coins[j])](0 <= j < len,len为coins数组长度)
     * ===> 即，累加所有f(i - coins[j]),得到f(i)结果;
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        // 目标值target的取值范围 ：[0,target]
        // ===> 所以需要去新创建一个大小为target + 1的数组;
        int[] temp = new int[target + 1];
        // 特殊情况 ：即，f(0)的情况（目标值为0的情况）
        // ===》 即，所有可能的排列数为1;
        temp[0] = 1;
        // 遍历所有可能的目标数 0 <= i <= target && i 为整数
        for(int i = 1; i <= target ; i ++){
            // 遍历nums数组中所有元素 && 为获取f(i)的值，则累加所有f(i - coins[j])的值
            // 需要注意的是，累加所有f(i - coins[j])的值需要满足条件 ：i >= coins[j];
            for (int num : nums) {
                // 必须要满足（i >= num）条件，才能够进行累加;
                if(i >= num){
                    // 一般情况 ：
                    // 状态转移方程 ：
                    // f(i) = add[f(i - coins[j])]
                    temp[i] += temp[i - num];
                }
            }
        }
        // 由于temp[i]所存储的是，目标值为i的所有可能排列数；
        // ===》 即，直接返回temp[target];
        return temp[target];
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：O（nt）;（n，为nums数组大小;t，为目标值target大小;）
     * （2）空间复杂度 ：O（t）;
     */
}
